The power of classical query languages is linked to the fact that they express a restricted class of declarative programs. The class of semantic objects expressible through queries in the relational calculus is limited in a number of helpful ways, for example, each such query is polynomial-time computable. Although relational calculus queries may not return finite results, a natural subclass of the relational calculus does, namely, the class of range-restricted queries. This class gives guarantees of finite output and is complete in that it captures all relational calculus queries whose outputs are always finite, i.e., safe queries. The class of range-restricted queries provides an effective syntax for safe queries, as every safe query is equivalent to a range-restricted one. However, the question of whether a relational calculus query is safe or not is known to be undecidable in conventional database systems.
The relational theory on which these results are based deals only with pure relational queries, that is, those containing no interpreted predicates. Practical query languages, in contrast, contain interpreted functions such as + and *. The resulting queries, then, make use of the domain semantics, rather than being independent of them as are pure relational queries. For example, if the underlying structure is the field of real numbers {character pullout}{character pullout}, +, *, 0,1, &lt;{character pullout}, the extension of relational calculus is achieved by using polynomial (in)equalities. For example, the query .phi.(x, y).tbd..E-backward.z.multidot.R (x, z){character pullout}R(z, y){character pullout}x.sup.2 +y.sup.2 =z defines a subset of the self-join operation with the condition that in joinable tuples (x, z) and (z, y), z must be the sum of squares of x and y. A natural question, then, is what sort of restrictions still apply to queries given with interpreted structure.
A problem related to safety is that of state-safety, that is, for a query and a database, determine if the output is finite. Unlike the safety problem, which are undecidable, the state-safety problem is decidable for some domains, such as natural numbers with the order relation. However, there are interpreted structures (even with decidable first-order theory) for which this problem is undecidable and for which the class of safe queries cannot be described syntactically.
Accordingly, there is a need for methods and apparatus for generating relational calculus queries in the context of certain types of database systems that are considered safe and thus solve the issues of undecidability and the lack of effective syntax.